//#define _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>
//
//void swap(int* key, int i, int j) {
//	int tmp = key[i];
//	key[i] = key[j];
//	key[j] = tmp;
//}
//
//void func(int* key, int begin,int end) {
//	if (begin == end) {
//		for (int i = 0; i <= end; i++) {
//			printf("%d ", key[i]);
//		}
//		printf("\n");
//	}
//	for (int i = begin; i <= end; i++) {
//		swap(key, begin, i);
//		func(key, begin + 1, end);
//		swap(key, i, begin);
//	}
//}
//
//int main() {
//	int n = 0;
//	scanf("%d", &n);
//	int* key = (int*)calloc(sizeof(int) * n);
//	for (int i = 0; i < n; i++) {
//		key[i] = i + 1;
//	}
//	func(key, 0, n - 1);
//	free(key);
//	return 0;
//}